<?php

/*
 * 单链表
 * @package
 * @author     wanglei@wyzc.com
 * @version    $Id$
 */

class node {
	public $id;
	public $data;
	public $next;

	public function __construct($id, $data, $next = null) {
		$this->id   = $id;
		$this->data = $data;
		$this->next = $next;
	}
}

class singleLink {

	private $head;
	//链表长度
	public $length;

	public function __construct(node $node) {
		$this->head   = $node;
		$this->length = 1;
	}

	/**
	 * 在链表尾部插入节点
	 * @param node $node
	 */
	public function append(node $node) {
		$current = $this->head;
		while (isset($current->next)) {
			$current = $current->next;
		}
		$current->next = $node;
		$this->length++;
	}

	/**
	 * 链表头部插入节点
	 * @param node $node
	 */
	public function insert(node $node) {
		$tmp        = $this->head;
		$this->head = $node;
		$node->next = $tmp;
		$this->length++;
	}


	/**
	 * 在链表中间插入节点
	 * @param node $node
	 * @param      $id
	 * @return bool
	 */
	public function insertInMiddle(node $node, $id) {
		$current = $this->head;
		while ($current) {
			if ($current->id == $id) {
				$oldNext       = $current->next;
				$current->next = $node;
				$node->next    = $oldNext;
				$this->length++;
			}
			$current = $current->next;
		}
		return false;
	}

	/**
	 * 遍历链表,可以传入函数参数在遍历中执行
	 * @param $callBack
	 */
	public function loop($callBack) {
		$current = $this->head;
		while ($current) {
			$callBack($current);
			$current = $current->next;
		}
	}

	/**
	 * 查询节点
	 * @param $id
	 * @return bool|node|null
	 */
	public function find($id) {
		$current = $this->head;
		while ($current) {
			if ($current->id == $id) {
				return $current;
			}
			$current = $current->next;
		}
		return false;
	}

	/**
	 * 更新节点
	 * @param $id
	 * @param $data
	 * @return bool
	 */
	public function update($id, $data) {
		$current = $this->head;
		while ($current) {
			if ($current->id == $id) {
				$current->data = $data;
			}
			$current = $current->next;
		}
		return false;
	}


	/**
	 * 删除节点
	 * @param $id
	 * @return bool
	 * @throws Exception
	 */
	public function delete($id) {
		if ($this->head->id == $id) {
			//删除head节点
			if (isset($this->head->next)) {
				$this->head = $this->head->next;
				$this->length--;
			}else{
				throw new Exception('不能删除唯一的head节点');
			}
		} else {
			$current = $this->head;
			while (isset($current->next)) {
				if ($current->next->id == $id) {
					$current->next = $current->next->next;
					$this->length--;
					return true;
				}
				$current = $current->next;
			}
		}
		return false;
	}
}

$list = new singleLink(new node(1, '山东'));
//尾插入
$list->append(new node(2, '北京'));
//头插入
$list->insert(new node(3, '西藏'));
//中间插入
$list->insertInMiddle(new node(6, '菏泽'), 3);
//链表长度
echo $list->length . PHP_EOL;

//通过id查询节点
$node = $list->find(3);
echo $node->data . PHP_EOL;

//更新节点
$list->update(3, '西双版纳');
$node = $list->find(3);
echo $node->data . PHP_EOL;
echo '-----------------' . PHP_EOL;

//删除节点
$list->delete(6);
$list->loop(function ($current) {
	echo $current->data . PHP_EOL;
});